package leetcode.editor.cn.q1_300.q50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author qidi
 * @date 2021-12-27 10:10:18
 */
class Q0090_SubsetsIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> cur = new LinkedList<>();
        boolean[] used;

        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            used = new boolean[nums.length];
            for (int n = 0; n <= nums.length; n++) {
                process(nums, n, 0);
            }
            return result;
        }

        private void process(int[] nums, int size, int start) {
            if (cur.size() == size) {
                result.add(new ArrayList<>(cur));
                return;
            }

            for (int i = start; i < nums.length - (size - cur.size()) + 1; i++) {
                // 如果当前元素和前一个元素相同，而且前一个元素没有被访问，说明前一个相同的元素在当前层已经被用过了
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
                cur.add(nums[i]);
                used[i] = true;
                process(nums, size, i + 1);
                cur.removeLast();
                used[i] = false;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0090_SubsetsIi().new Solution();
        System.out.println(solution.subsetsWithDup(new int[]{1, 2, 2}));
    }
}